home *** CD-ROM | disk | FTP | other *** search
/ Games of Daze / Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso / x2ftp / msdos / theory / lansd / readme < prev   
Encoding:
Text File  |  1994-08-30  |  13.5 KB  |  232 lines
  1. My master's thesis, "Texture Mapping and Resampling for Computer Graphics",
  2. is now available for electronic access. The thesis is an in-depth examination
  3. of the entire texture mapping process, starting with simple introductory
  4. concepts and ending with a discussion of new state-of-the-art texture
  5. filtering algorithms developed during the course of this thesis research work.
  6.  
  7. The thesis is geared to beginners and experts alike. The first half of the
  8. thesis introduces the concepts of texture mapping, how texture coordinates
  9. are assigned to surfaces (the parameterization), how texture is rendered
  10. onto a surface, and why a texture image must be filtered before it is applied
  11. to an object (72 pages). This is then followed by a review of current and 
  12. popular texture filtering algorithms (MIPmapping, summed area tables, 
  13. stochastic and adaptive supersampling) which are analyzed and related to the 
  14. filtering theory outlined in previous sections of the thesis.
  15.  
  16. All material is presented in a non-mathematical, conceptual nature with dozens 
  17. of accompanying illustrations for clarification. For the expert, most concepts
  18. are expanded upon with some form of semi-rigorous, mathematical explanation. 
  19.  
  20. The "Texture Resampling Process" chapter is of particular interest to any 
  21. reader wishing to gain an insight into the concepts and mathematical theory 
  22. behind the resampling of a 2D image onto an arbitrarily-oriented plane in 
  23. 3-space (in other words, how to texture map a 2D image onto a 3D object with 
  24. no artifacts appearing in the final image).
  25.  
  26. The latter half of the thesis introduces the EWA and NIL image filtering 
  27. techniques and how they were incorporated into the author's scanline rendering
  28. system as texture filtering algorithms. The thesis results show that the EWA 
  29. filter produces higher quality textured images than that of the common MIPmap 
  30. texture filtering algorithm, yet with only slight decrease in rendering speed.
  31.  
  32. The appendices also include a conceptual tutorial on parametric curves and 
  33. surfaces, and an interesting discussion of how to add an accumulation buffer
  34. to a scanline renderer so that depth-of-field, motion blur and pseudo-stochastic
  35. anti-aliasing can be simulated. 
  36.  
  37. The thesis is 163 pages of single-spaced text, with 58 illustrations and 8 
  38. tables. The uncompressed Postscript file is 9.5Mb in size. It can be viewed 
  39. with an appropriate Postscript viewer or printed to any Postscript printer. 
  40. Note that it is very important to have the print density on the laser printer 
  41. cartridge set properly so that the bitmap images do not get printed overly 
  42. dark.
  43.  
  44. Appended to this message are:
  45.  
  46.     1) How to obtain this thesis by FTP
  47.     2) Abstract from the thesis
  48.     3) Table of contents from the thesis
  49.  
  50. Please contact lansd@dgp.toronto.edu if you have any further questions or
  51. problems. The thesis is Copyright (c) 1991 by Robert C. Lansdale.
  52.  
  53. ------------------------->>>>  How to FTP  <<<<------------------------------
  54.  
  55. To obtain a copy by anonymous FTP, please use the following procedure:
  56.  
  57.   % ftp explorer.dgp.toronto.edu     <--- or: 128.100.4.1 --->
  58.  
  59.   Name (explorer.dgp.toronto.edu:lansd): anonymous
  60.   Password: {---> type your name & address here,  e.g. lansd@dgp.toronto.edu <---}
  61.  
  62.   ftp> cd pub/lansd
  63.   ftp> binary
  64.   ftp> get lansd.ps.Z
  65.   ftp> quit
  66.   % uncompress lansd.ps.Z
  67.   % lpr -P{---postscript-printer---} lansd.ps
  68.  
  69. Notes: 
  70.     1. The Postscript file includes several bitmap images and will render 
  71.        best on a 300 dpi laser printer.
  72.     2. Anonymous FTP is only accepted from hosts that are running the
  73.        finger daemon.
  74.  
  75. --------------------------->>>>  Abstract  <<<<-------------------------------
  76.  
  77. Texture mapping is a popular rendering technique used in three-dimensional 
  78. computer graphics. It allows textures represented as digital images to be 
  79. mapped across surfaces in a 3D scene, providing a simple method for adding 
  80. realistic detail to computer generated imagery. The process of transforming 
  81. a discrete 2D texture image onto a 3D surface and subsequently onto the 2D 
  82. projection window (the screen) is called image resampling. Deformations 
  83. applied to the texture image during this process often lead to visual 
  84. artifacts in the textured surface, many of which result from frequencies 
  85. in the transformed texture image too high for the output display to reproduce.
  86. These artifacts can be removed by filtering the texture in accordance with 
  87. digital signal filtering theory.
  88.  
  89. Texture filtering removes high frequencies from the texture image before it is 
  90. resampled to the screen. Since this tends to be an expensive operation, 
  91. researchers have developed several cost effective, constant-time techniques. 
  92. These techniques allow the filtering operation to be performed in a bounded 
  93. number of accesses to the texture image, independent of the image's size. 
  94. However, approximations of the ideal filtering process with low quality, 
  95. space-invariant filter functions tend to produce poor results. 
  96.  
  97. The major contribution of this thesis is the adaptation and implementation of 
  98. two recently published high-quality, space-variant, constant-time filtering 
  99. techniques into the author's NuGraf-3d scanline rendering system. These are 
  100. the "Elliptical Weighted Average Filter" by Greene and Heckbert and the 
  101. "NIL Constant-Time Space-Variant Filter" by Fournier and Fiume.
  102.  
  103. A second significant contribution of this thesis is the development of stable 
  104. surface parameterizations for projective and affine mappings. The solutions 
  105. presented are applicable both to texture mapping and to other applications. 
  106. The thesis also provides a thorough overview of all phases of the texture 
  107. mapping process, including a tutorial of 1D and 2D filtering theory, and a 
  108. detailed review of existing filtering techniques. An appendix describes how 
  109. uniform and stochastic supersampling, depth-of-field and motion blur were 
  110. accommodated in NuGraf-3d with the addition of an accumulation buffer.
  111.  
  112. ----------------------->>>>  Table of Contents  <<<<--------------------------
  113.  
  114. 0  Introduction
  115.  
  116.    0.1 Thesis Overview  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :   3
  117.    0.2 Contributions of Thesis   : : : : : : : : : : : : : : : : : : : : : : : : : : : : :   5
  118.  
  119. 1  The Texturing Process
  120.  
  121.    1.1 Applications of Texturing To Computer Graphics  : : : : : : : : : : : : : : :   7
  122.    1.2 The Texturing Process  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :   8
  123.        1.2.1 Texture Function Selection  : : : : : : : : : : : : : : : : : : : : : : :   8
  124.        1.2.2 The Texture "Map" Derivation  : : : : : : : : : : : : : : : : : : : : :  10
  125.        1.2.3 Texture Distortion Control  : : : : : : : : : : : : : : : : : : : : : : :  10
  126.        1.2.4 Rendering Textured Surfaces  : : : : : : : : : : : : : : : : : : : : : :  10
  127.    1.3 Extended Applications of Texture Filtering  : : : : : : : : : : : : : : : : : :  11
  128.  
  129. 2  Surface Parameterization, Geometric Mappings, and Accurate Texture Rendering
  130.  
  131.    2.1 Composing the Compound Texture Map  : : : : : : : : : : : : : : : : : : :  14
  132.        2.1.1 Derivation of the Surface Parameterization  : : : : : : : : : : : : : :  15
  133.        2.1.2 Induced Geometric Surface Parameterizations  : : : : : : : : : : : : :  17
  134.        2.1.3 The Projective Surface Parameterization : : : : : : : : : : : : : : : :  18
  135.              2.1.3.1 Computing an Induced Projective Surface Parameterization   20
  136.    2.2 Interpolation Anomalies in a Scanline Renderer  : : : : : : : : : : : : : : : :  22
  137.        2.2.1 Corrective Solutions to Interpolation Anomalies : : : : : : : : : : : :  24
  138.        2.2.2 Retrofitting NuGraf-3d for Accurate Texturing  : : : : : : : : : : : :  26
  139.    2.3 Summary  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  29
  140.  
  141. 3  The Texture Resampling Process
  142.  
  143.    3.1 The Texture Resampling Problem   : : : : : : : : : : : : : : : : : : : : : : :  32
  144.    3.2 Resampling in the One-Dimensional Domain   : : : : : : : : : : : : : : : : :  35
  145.        3.2.1 Introduction to Aliasing in 1D Signals  : : : : : : : : : : : : : : : : :  35
  146.        3.2.2 An Overview of 1D Signal Processing   : : : : : : : : : : : : : : : : :  38
  147.              3.2.2.1 Filtering Basics   : : : : : : : : : : : : : : : : : : : : : : : :  39
  148.              3.2.2.2 Reconstruction Filters  : : : : : : : : : : : : : : : : : : : : :  42
  149.              3.2.2.3 Discrete Convolution   : : : : : : : : : : : : : : : : : : : : :  44
  150.        3.2.3 A Naive Implementation of 1D Signal Resampling  : : : : : : : : : :  45
  151.        3.2.4 The Ideal Resampling Process in 1D  : : : : : : : : : : : : : : : : : :  47
  152.    3.3 Extension to 2D Filtering  : : : : : : : : : : : : : : : : : : : : : : : : : : : :  51
  153.    3.4 2D Resampling Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : :  52
  154.        3.4.1 The Screen-Space-Based Ideal 2D Resampling Process  : : : : : : : :  54
  155.        3.4.2 The Texture-Space-Based Ideal Resampling Process  : : : : : : : : :  56
  156.              3.4.2.1 Space-Invariant Filtering  : : : : : : : : : : : : : : : : : : :  58
  157.              3.4.2.2 Space-Variant Filtering  : : : : : : : : : : : : : : : : : : : :  59
  158.    3.5 Approximating the Ideal Resampling Process  : : : : : : : : : : : : : : : : :  59
  159.        3.5.1 Space-Variant Filtering with Direct Convolution  : : : : : : : : : : :  61
  160.              3.5.1.1 Non-Uniform Resampling with Direct Convolution  : : : : :  62
  161.              3.5.1.2 Retrospective on Direct Convolution : : : : : : : : : : : : :  63
  162.        3.5.2 Constant-Time Direct Convolution Techniques  : : : : : : : : : : : :  63
  163.              3.5.2.1 The MIP mapping Technique  : : : : : : : : : : : : : : : : :  64
  164.              3.5.2.2 The Summed-Area Table Technique  : : : : : : : : : : : : :  65
  165.        3.5.3 Non-uniform Resampling with Ideal Supersampling : : : : : : : : : :  67
  166.        3.5.4 Supersampling  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  68
  167.              3.5.4.1 Adaptive Supersampling   : : : : : : : : : : : : : : : : : : :  70
  168.              3.5.4.2 Stochastic Sampling  : : : : : : : : : : : : : : : : : : : : : :  71
  169.    3.6 Preview of the EWA and NIL Filtering Techniques  : : : : : : : : : : : : : :  72
  170.    3.7 Summary  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  73
  171.  
  172. 4  The Elliptical Weighted Average Filter
  173.  
  174.    4.1 The EWA Resampling Filter   : : : : : : : : : : : : : : : : : : : : : : : : : :  75
  175.    4.2 Overview of the EWA Filtering Technique  : : : : : : : : : : : : : : : : : : :  76
  176.        4.2.1 Operation of the EWA Filter  : : : : : : : : : : : : : : : : : : : : : :  77
  177.        4.2.2 Example Run-Through of the EWA Filter  : : : : : : : : : : : : : : :  80
  178.    4.3 Implementation of EWA in NuGraf-3d  : : : : : : : : : : : : : : : : : : : : :  82
  179.    4.4 EWA Filter Extensions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  84
  180.    4.5 Performance Test Results  : : : : : : : : : : : : : : : : : : : : : : : : : : : :  87
  181.    4.6 Shortcomings of the EWA Filter  : : : : : : : : : : : : : : : : : : : : : : : :  88
  182.    4.7 Extending EWA for use with Arbitrary Filter Functions  : : : : : : : : : : :  89
  183.    4.8 Future Work   : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  90
  184.    4.9 Summary  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :  91
  185.  
  186. 5  NIL - Constant-Time, Space-Variant Filtering
  187.  
  188.    5.1 Introduction to the NIL Filtering Process  : : : : : : : : : : : : : : : : : : :  94
  189.        5.1.1 Providing for Oddly-Shaped Convolution Mask Regions  : : : : : : :  94
  190.        5.1.2 Example Use of the NIL Filtering Technique   : : : : : : : : : : : : :  98
  191.    5.2 Extensions to the NIL Filtering Algorithm : : : : : : : : : : : : : : : : : : : 101
  192.        5.2.1 Extending NIL into a Unified Resampling Technique  : : : : : : : : : 102
  193.        5.2.2 Improving the Convolution Mask Area Approximation  : : : : : : : : 104
  194.        5.2.3 New Patch Subdivision Techniques  : : : : : : : : : : : : : : : : : : : 105
  195.    5.3 Applying NIL to the Checkerboard Test Image  : : : : : : : : : : : : : : : : 109
  196.    5.4 NIL as a "Texture Manipulation" Tool  : : : : : : : : : : : : : : : : : : : : : 110
  197.    5.5 Future Work   : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 112
  198.    5.6 Summary  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 114
  199.  
  200. 6  Conclusions
  201.  
  202.    6.1 Comparison of the MIP map, Supersampling, EWA & NIL Techniques  : : : 116
  203.    6.2 Future Work   : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 117
  204.    6.3 Retrospective  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 118
  205.  
  206. A  Example Images Using Explicit and Induced Surface Parameterizations
  207.  
  208.    A.1 Image 1  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 119
  209.    A.2 Image 2  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 119
  210.  
  211. B  The 2D-3D Projective Surface Parameterization Algorithm
  212.  
  213. C  Reparameterizing the 4x4 Orthographic Projection Matrix into a 4x3 Matrix
  214.  
  215. D  The Fourier Transform
  216.  
  217. E  Fourier Convolution
  218.  
  219. F  Parametric Curves and Surfaces
  220.  
  221.    F.1 Parametric Curves  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 137
  222.        F.1.1 Example Application of an Order 2 (Bilinear) Curve  : : : : : : : : : 138
  223.    F.2 Parametric Surfaces   : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 139
  224.  
  225. G  Integration of NIL into NuGraf-3d
  226.  
  227. H  Application of an Accumulation Buffer in NuGraf-3d
  228.  
  229.    H.1 Depth-of-field Effects  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 145
  230.    H.2 Stochastic and Supersampled Anti-aliasing : : : : : : : : : : : : : : : : : : : 148
  231.    H.3 Motion Blur : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 151
  232.